package com.剑指offer.第六章;

import java.util.Stack;

/**
 * 输入一个数组，它的每个数字是某天的温度。请计算每天需要等几天才会出现更高的温度。例如：如果输入数组[35,31,33,36,34]，那么
 * 输出为[3,1,1,0,0]
 * <p>
 * 解题思路：使用栈保存每个温度的下标位置，当前的温度与栈顶的位置的温度进行比较
 */
public class 每日温度 {

    public static int[] resolve(int[] nums) {
        int[] ints = new int[nums.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length; i++) {
            while (!stack.empty() && nums[i] > nums[stack.peek()]) {
                Integer pop = stack.pop();
                ints[pop] = i - pop;
            }
            stack.push(i);
        }
        return ints;
    }

    public static void main(String[] args) {
        int[] n = new int[]{35, 31, 33, 36, 34};
        int[] resolve = resolve(n);
        for (int i : resolve) {
            System.out.println(i);
        }
    }
}
